package 贪心算法.无重叠区间;

import java.util.*;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/1/31 16:46
 * @description:
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        int[][] array = {{1,100},{11,22},{1,11},{2,12}};
        System.out.println(eraseOverlapIntervals(array));
    }


    //贪心算法
    public static int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }

        //对二维数组进行排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[1] - interval2[1];
            }
        });

        int n = intervals.length;
        int right = intervals[0][1];
        int ans = 1;
        //妙啊
        for (int i = 1; i < n; ++i) {
            if (intervals[i][0] >= right) {
                ++ans;
                right = intervals[i][1];
            }
        }
        return n - ans;
    }
}
